import bisect
import math
from bisect import bisect_left, bisect_right
from collections import deque
from functools import cache
from itertools import pairwise, accumulate
from string import ascii_lowercase
from .data_struct import *
from sortedcontainers import SortedList


def solution_100191(word: str) -> int:
    """
    index : 3014
    """
    if len(word) <= 8:
        return len(word)
    if len(word) <= 16:
        return (len(word) - 8) * 2 + 8
    if len(word) <= 24:
        return (len(word) - 16) * 3 + 24
    return (len(word) - 24) * 4 + 48


def solution_100188(n: int, x: int, y: int) -> List[int]:
    """
    index:3015
    """
    # floyd
    # 超时
    f = [[10 ** 18] * n for i in range(n)]
    f[x - 1][y - 1], f[y - 1][x - 1] = 1, 1
    for i in range(n):
        f[i][i] = 0
    for i in range(n - 1):
        f[i][i + 1], f[i + 1][i] = 1, 1
    for k in range(n):
        for i in range(n):
            for j in range(n):
                f[i][j] = min(f[i][j], (f[i][k] + f[k][j]))
    res = [0] * n
    for i in range(n):
        for j in range(n):
            res[f[i][j] - 1] += 1
    res[-1] = 0
    return res


def solution_100188_2(n: int, x: int, y: int) -> List[int]:
    # 暴力做法:BFS
    # 每个点花费O(n)求出它到其余点的距离
    # 花费O(n^2)时间求出所有结果
    res = [0] * n
    x = x - 1
    y = y - 1
    # 只往后找,因此每次结果加+2
    for i in range(n):
        for j in range(i + 1, n):
            d1 = j - i  # 直接走
            d2 = abs(i - x) + 1 + abs(j - y)  # i->x->y->j
            d3 = abs(i - y) + 1 + abs(j - x)  # i->y->x->j
            min_d = min(d1, d2, d3)
            res[min_d - 1] += 2
    return res


def solution_100192(word: str) -> int:
    """
    index: 3016
    """
    f = [0] * 26
    for ch in word:
        f[ord(ch) - ord('a')] += 1
    f.sort(reverse=True)
    res = 0
    res += sum(f[0:8])
    res += sum(f[8:16] * 2)
    res += sum(f[16:24] * 3)
    res += sum(f[24:] * 4)
    return res


def solution_100192_2(word: str) -> int:
    # 排序不等式
    cnt = Counter[str](word)
    a = sorted(cnt.values(), reverse=True)
    ans = 0
    for i, c in enumerate(a):
        ans += c * (i // 8 + 1)
    return ans


def solution_100215(s: str) -> int:
    tmp = s.lower()
    cnt = 0
    for i in range(len(tmp) - 1):
        if tmp[i] != tmp[i + 1]:
            cnt += 1
    return cnt


def solution_100206(nums: List[int]) -> int:
    f = {}
    for num in nums:
        if num not in f:
            f[num] = 1
        else:
            f[num] += 1
    max_cnt = 1
    # 从f中拿就可以了
    for num in nums:
        cnt = 2
        # cnt = f[num]- (f[num]%2^1)
        if num == 1 and f[num] % 2 == 0:
            cnt = f[num] - 1
        elif num == 1 and f[num] % 2 != 0:
            cnt = f[num]
        elif f[num] >= 2:
            tmp = num
            while True:
                tmp = tmp * tmp
                if tmp not in f:
                    cnt -= 1
                    break
                elif f[tmp] == 1:
                    cnt += 1
                    break
                elif f[tmp] >= 2:
                    cnt += 2
        else:
            cnt -= 1
        max_cnt = max(max_cnt, cnt)
    return max_cnt


def solution_100195(n: int, m: int) -> int:
    even_x = (n + 1) // 2
    even_y = (m + 1) // 2
    odd_x = n - even_x
    odd_y = m - even_y
    return even_x * odd_y + even_y * odd_x
    # return n*m//2


def solution_100179(nums: List[int], k: int) -> int:
    """
    1. 拆位
    2. 试填法
    3. 相邻合并 -> 连续子数组合并

    从左到右考虑数字
    如果某一段数字能合并成0，那么操作次数就是这一段的长度-1
    如果某一段数字不能合并成0，那么操作次数就是这一段的长度（从其他地方借0）

    考虑每一位的时候，需要带上高位可以变成0的位
    """
    ans = mask = 0  # mask表示需要考虑的位置
    for b in range(29, -1, -1):
        mask |= 1 << b  # 当前考虑的位
        cnt = 0
        and_res = -1  # 全为1的数字
        for x in nums:
            and_res &= x & mask
            if and_res:
                cnt += 1  # 还得合并
            else:  # 这一段合并完了
                and_res = -1  # 合并下一段
        # 题目条件 k<len(nums), 故cnt > k时视为无法变0
        if cnt > k:
            ans |= 1 << b
            mask ^= 1 << b  # 反悔，这一位不要了，因为他只能是1
    return ans


def solution_100222(nums: List[int]) -> str:
    if not nums[0] + nums[1] > nums[2]:
        return 'none'
    if not nums[0] + nums[2] > nums[1]:
        return 'none'
    if not nums[1] + nums[2] > nums[0]:
        return 'none'
    ms = set()
    for num in nums:
        ms.add(num)
    if len(ms) == 1:
        return 'equilateral'
    if len(ms) == 2:
        return 'isosceles'
    if len(ms) == 3:
        return 'scalene'


def solution_100194(points: List[List[int]]) -> int:
    cnt = 0
    for point1 in points:
        for point2 in points:
            if point1 == point2:
                continue
            if point1[0] <= point2[0] and point1[1] >= point2[1]:
                flag = False
                for point3 in points:
                    if point3 == point2 or point3 == point1:
                        continue
                    if point1[0] <= point3[0] <= point2[0] and point1[1] >= point3[1] >= point2[1]:
                        flag = True
                        break
                if flag:
                    continue
                else:
                    cnt += 1
    return cnt


def solution_100183(nums: List[int], k: int) -> int:
    """
    超时
    """
    s = [0]
    for i in range(1, len(nums) + 1):
        s.append(s[i - 1] + nums[i - 1])
    f = {}
    for i, x in enumerate(nums):
        if x not in f:
            f[x] = [i]
        else:
            f[x].append(i)
    max_sum = -10 ** 19
    for i, x in enumerate(nums):
        tmp = x + k
        if tmp in f:
            for index in f[tmp]:
                if index > i:
                    max_sum = max(max_sum, s[index + 1] - s[i])
        tmp = x - k
        if tmp in f:
            for index in f[tmp]:
                if index > i:
                    max_sum = max(max_sum, s[index + 1] - s[i])
    return max_sum if max_sum > -10 ** 19 else 0


def solution_100193(points: List[List[int]]) -> int:
    # 排序, 保证按照横坐标从小到大排序，后续枚举只需要考虑纵坐标
    # 横坐标相同时，按纵坐标从大到小排序
    points.sort(key=lambda p: (p[0], -p[1]))
    ans = 0
    for i, (_, y0) in enumerate(points):
        max_y = -inf
        for (_, y1) in points[i + 1:]:
            if max_y < y1 <= y0:
                max_y = y1
                ans += 1
    return ans


def solution_100214(nums: List[int]) -> int:
    s = 0
    cnt = 0
    for num in nums:
        s += num
        if s == 0:
            cnt += 1
    return cnt


def solution_100204(word: str, k: int) -> int:
    n = len(word)
    cnt = (n + k - 1) // k
    for i in range(k, n, k):
        length = n - i
        if word[0:length] == word[i:i + length]:
            cnt = min(i // k, cnt)
    return cnt


def solution_100189(image: List[List[int]], threshold: int) -> List[List[int]]:
    def check(center):
        x, y = center[0], center[1]
        for i in range(x - 1, x + 2, 1):
            if abs(image[i][y - 1] - image[i][y]) > threshold or abs(image[i][y] - image[i][y + 1]) > threshold:
                return False
        for i in range(y - 1, y + 2, 1):
            if abs(image[x - 1][i] - image[x][i]) > threshold or abs(image[x][i] - image[x + 1][i]) > threshold:
                return False
        return True

    m = len(image)
    n = len(image[0])
    result = [[-1] * n for _ in range(m)]
    for i in range(1, m - 1):
        for j in range(1, n - 1):
            center = (i, j)
            if check(center):
                result[i][j] = (sum(image[i - 1][j - 1:j + 2]) + sum(image[i][j - 1:j + 2]) + sum(
                    image[i + 1][j - 1:j + 2])) // 9
    cnt = [[0] * n for _ in range(m)]
    for i in range(1, m - 1):
        for j in range(1, n - 1):
            if result[i][j] != -1:
                x, y = i, j
                for k in range(x - 1, x + 2):
                    for s in range(y - 1, y + 2):
                        if cnt[k][s] > 0:
                            image[k][s] = image[k][s] + result[i][j]
                        else:
                            image[k][s] = result[i][j]
                        cnt[k][s] += 1
    for i in range(m):
        for j in range(n):
            if cnt[i][j] > 0:
                image[i][j] = image[i][j] // cnt[i][j]

    return image


def solution_100203(word: str, k: int) -> int:
    return solution_100204(word, k)


def solution_100230(matrix: List[List[int]]) -> List[List[int]]:
    n = len(matrix)
    m = len(matrix[0])
    ans = [[-1] * m for _ in range(n)]
    tmp = set()
    for j in range(m):
        tmp.clear()
        max_c = -1
        for i in range(n):
            if matrix[i][j] != -1:
                ans[i][j] = matrix[i][j]
                max_c = max(max_c, matrix[i][j])
            else:
                tmp.add(i)
        for index in tmp:
            ans[index][j] = max_c
    return ans


def solution_100186(nums: List[int], pattern: List[int]) -> int:
    n = len(nums)
    m = len(pattern)
    cnt = 0
    for i in range(n - m):
        flag = True
        for j in range(m):
            if pattern[j] == 1:
                if nums[i + j + 1] <= nums[i + j]:
                    flag = False
                    break
            elif pattern[j] == 0:
                if nums[i + j + 1] != nums[i + j]:
                    flag = False
                    break
            elif pattern[j] == -1:
                if nums[i + j + 1] >= nums[i + j]:
                    flag = False
                    break
        if flag:
            cnt += 1
    return cnt


def solution_100219(words: List[str]) -> int:
    """
    奇回文串的特点：偶回文串的特点 + 正中间任意填 -> 最后再填

    优先填短的

    只考虑左半边怎么填
    """
    # n = len(words)
    # arrays = [0] * 26
    # lens = [len(x) for x in words]
    # lens.sort()
    # cnt = 0
    # for word in words:
    #     for char in word:
    #         arrays[ord(char) - ord('a')] += 1
    # for length in lens:
    #     flag = False
    #     if length % 2 == 0:
    #         for i in range(26):
    #             if arrays[i] >= length:
    #                 arrays[i] -= length
    #                 length = 0
    #                 flag = True
    #             if arrays[i] % 2 == 0:
    #                 length -= arrays[i]
    #                 arrays[i] = 0
    #             else:
    #                 length -= (arrays[i] - 1)
    #                 arrays[i] = 1
    #
    #     if flag:
    #         cnt += 1
    cnt = Counter[int]()
    for word in words:
        cnt += Counter[int](word)

    # 计算可用来组成回文串左右两侧的字母个数
    # 只需统计一侧可用字母个数
    left = sum(c // 2 for c in cnt.values())
    # 按照字符串长度，从小到大填入字母
    ans = 0
    words.sort(key=len)
    for word in words:
        m = len(word) // 2
        if left < m:
            break
        left -= m  # 拿出m个字符放入word
        ans += 1
    # 不用管奇数的情况
    # 最后留着没用的字符可以随便填上去
    return ans


def solution_100198(nums: List[int], pattern: List[int]) -> int:
    """
    KMP
    """
    n = len(nums)
    m = len(pattern)
    cnt = 0

    def compute_next(p):
        ret = [0] * m
        ret[0] = -1
        j = -1
        for k in range(1, m):
            while j > -1 and pattern[j + 1] != pattern[k]:
                j = ret[j]
            if p[j + 1] == pattern[k]:
                j += 1
            ret[k] = j
        return ret

    pat_next = compute_next(pattern)
    q = -1
    tmp = []
    for i in range(n - 1):
        cur = nums[i + 1] - nums[i]
        if cur > 0:
            tmp.append(1)
        elif cur == 0:
            tmp.append(0)
        else:
            tmp.append(-1)
    for i in range(n - 1):
        while q > -1 and pattern[q + 1] != tmp[i]:
            q = pat_next[q]
        if pattern[q + 1] == tmp[i]:
            q += 1
        if q == m - 1:
            cnt += 1
            q = pat_next[q]

    return cnt


def solution_100198_2(nums: List[int], pattern: List[int]) -> int:
    """
    Z 函数

    把 pattern 拼在b前面
    中间插入间隔符

    根据Z函数的定义，只要z[i] = m,就找到了1个匹配
    """
    m = len(pattern)
    pattern.append(2)
    pattern.extend((y > x) - (y < x) for x, y in pairwise(nums))

    n = len(pattern)
    z = [0] * n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(z[i - l], r - i + 1)
        while i + z[i] < n and pattern[z[i]] == pattern[i + z[i]]:
            l, r = i, i + z[i]
            z[i] += 1
    return sum(lcp == m for lcp in z[m + 1:])


def solution_100221(nums: List[int]) -> int:
    if len(nums) <= 2:
        return 1
    cnt = 1
    score = nums[0] + nums[1]
    for i in range(2, len(nums) - 1, 2):
        if nums[i] + nums[i + 1] == score:
            cnt += 1
        else:
            return cnt
    return cnt


def solution_100211(s: str) -> str:
    f = defaultdict(lambda: 0)
    idx = {}
    for i in range(len(s)):
        f[s[i]] += 1
        idx[s[i]] = i
    max_cnt = 0
    for ch in f:
        if f[ch] > max_cnt:
            max_cnt = f[ch]
    res = []
    for ch in f:
        if f[ch] == max_cnt:
            res.append((idx[ch], ch))
    res.sort()
    ans = ''
    for _, ch in res:
        ans += ch
    return ans


def solution_100220(nums: List[int]) -> int:
    if len(nums) <= 2:
        return 1

    @cache
    def dfs(i, j, score, cnt):
        if i >= j:
            return cnt
        if nums[i] + nums[i + 1] == score:
            ans1 = dfs(i + 2, j, score, cnt + 1)
        else:
            ans1 = cnt
        if nums[j - 1] + nums[j] == score:
            ans2 = dfs(i, j - 2, score, cnt + 1)
        else:
            ans2 = cnt
        if nums[i] + nums[j] == score:
            ans3 = dfs(i + 1, j - 1, score, cnt + 1)
        else:
            ans3 = cnt
        return max(ans1, ans2, ans3)

    return max(dfs(2, len(nums) - 1, nums[0] + nums[1], 1),
               dfs(0, len(nums) - 3, nums[-2] + nums[-1], 1),
               dfs(1, len(nums) - 2, nums[0] + nums[-1], 1))


def solution_100205(nums: List[int]) -> int:
    # nums.sort()
    # inc = -1
    # cur = nums[0]
    # index = 0
    # w = -inf
    # i = 0
    # while i < len(nums) - 1:
    #     i += 1
    #     cur += 1
    #     if nums[i] == cur:
    #         continue
    #     elif nums[i] - cur == -1 and inc < 0:
    #         inc = i
    #     elif nums[i] - cur == -1 and inc >= 0:
    #         inc = i
    #     elif nums[i] - cur == -2 and inc < 0:
    #         inc = i
    #     else:
    #         w = max(i - index, w)
    #         if inc >= 0:
    #             i = inc
    #         cur = nums[i]
    #         index = i
    #         inc = -1
    # w = max(len(nums) - index, w)
    # return w
    nums.sort()
    f = defaultdict(int)
    for num in nums:
        f[num + 1] = f[num] + 1  # 当前数加1, 可以使得上个为num的数后续增加一个数字
        # 先算num+1, 否则会重复计算自身
        f[num] = f[num - 1] + 1  # 当前数不加1, 可以使得上个为num-1的数后续增加一个数字
    return max(f.values())


def solution_100212(words: List[str]) -> int:
    def isPrefixAndSuffix(str1, str2):
        if len(str1) > len(str2):
            return False
        n = len(str1)
        m = len(str2)
        if str1 != str2[0:n]:
            return False
        if str1 != str2[m - n:]:
            return False
        return True

    cnt = 0
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if isPrefixAndSuffix(words[i], words[j]):
                cnt += 1
    return cnt


def solution_100217(mat: List[List[int]]) -> int:
    m = len(mat)
    n = len(mat[0])

    def check(c):
        if c < 10:
            return False
        for i in range(2, int(c ** 0.5) + 1):
            if c % i == 0:
                return False
        return True

    def get_one(x0, y0, x, y):
        res = []
        cur = 0
        while -1 < x0 < m and -1 < y0 < n:
            cur = cur * 10 + mat[x0][y0]
            if check(cur):
                res.append(cur)
            x0 += x
            y0 += y
        return res

    f = defaultdict(int)
    for i in range(m):
        for j in range(n):
            if cur := get_one(i, j, 1, 0):
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, -1, 0)) != -1:
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, 1, 1)) != -1:
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, -1, 1)) != -1:
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, 0, 1)) != -1:
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, 1, -1)) != -1:
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, -1, -1)) != -1:
                for x in cur:
                    f[x] += 1
            if (cur := get_one(i, j, 0, -1)) != -1:
                for x in cur:
                    f[x] += 1

    max_cnt = -1
    max_num = -1
    for num in f:
        if f[num] == max_cnt:
            max_num = max(num, max_num)
        elif f[num] > max_cnt:
            max_cnt = f[num]
            max_num = num
    return max_num


def weekly_contest_386_solution_1(nums: List[int]) -> bool:
    cnt = Counter[int](nums)
    if max(cnt.values()) >= 3:
        return False
    else:
        return True


def biweekly_contest_125_solution_1(nums: List[int], k: int) -> int:
    cnt = 0
    for num in nums:
        if num < k:
            cnt += 1
    return cnt


def biweekly_contest_125_solution_2(nums: List[int], k: int) -> int:
    heapq.heapify(nums)
    cnt = 0
    while nums[0] < k and len(nums) >= 2:
        t1 = heapq.heappop(nums)
        t2 = heapq.heappop(nums)
        t3 = min(t1, t2) * 2 + max(t1, t2)  # t3 = t1*2 + t2
        heapq.heappush(nums, t3)
        cnt += 1
    return cnt


def biweekly_contest_125_solution_3(edges: List[List[int]], signalSpeed: int) -> List[int]:
    n = len(edges) + 1
    f = defaultdict(dict)
    for a, b, w in edges:
        f[a][b] = w
        f[b][a] = w

    @cache
    def dfs(x, p, distance):
        res = 0
        if distance % signalSpeed == 0:
            res += 1
            distance = 0
        # 无效遍历太多
        # for i in range(n):
        #     if i != p and i in f[x]:
        #         res += dfs(i, x, distance + (f[x][i] % signalSpeed))
        for i in f[x]:
            if i != p:
                res += dfs(i, x, distance + (f[x][i] % signalSpeed))
        return res

    count = [0] * n
    for i in range(n):
        total_len = 0
        for j in f[i]:
            res = dfs(j, i, f[i][j])
            count[i] += res * total_len
            total_len += res
    return count


def weekly_contest_387_solution_1(nums: List[int]) -> List[int]:
    arr1 = [nums[0]]
    arr2 = [nums[1]]
    for num in nums[2:]:
        if arr1[-1] > arr2[-1]:
            arr1.append(num)
        else:
            arr2.append(num)
    return arr1 + arr2


def weekly_contest_387_solution_2(grid: List[List[int]], k: int) -> int:
    m = len(grid)
    n = len(grid[0])
    ans = [[0] * (n + 1) for _ in range(m + 1)]
    cnt = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if i == j == 0:
                continue
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + grid[i - 1][j - 1]
            if ans[i][j] <= k:
                cnt += 1
    return cnt


def weekly_contest_387_solution_3(grid: List[List[int]]) -> int:
    n = len(grid)
    mid = (n // 2) + 1
    cnt = defaultdict(int)
    for i in range(mid):
        cnt[grid[i][i]] += 1
        cnt[grid[i][n - 1 - i]] += 1
        cnt[grid[mid - 1 + i][mid - 1]] += 1
    cnt[grid[mid - 1][mid - 1]] -= 2
    cnt_total = defaultdict(int)
    for i in range(n):
        for j in range(n):
            cnt_total[grid[i][j]] += 1
    cnt_total[0] -= cnt[0]
    cnt_total[1] -= cnt[1]
    cnt_total[2] -= cnt[2]
    tiles = (mid - 1) * 3 + 1
    tiles_total = n * n - tiles

    # i = 0
    changes_1 = tiles - cnt[0]
    changes_2 = min(tiles_total - cnt_total[1], tiles_total - cnt_total[2])
    changes = changes_1 + changes_2
    # i = 1
    changes_1 = tiles - cnt[1]
    changes_2 = min(tiles_total - cnt_total[0], tiles_total - cnt_total[2])
    changes = min(changes, changes_1 + changes_2)
    # i = 2
    changes_1 = tiles - cnt[2]
    changes_2 = min(tiles_total - cnt_total[0], tiles_total - cnt_total[1])
    changes = min(changes, changes_1 + changes_2)

    # for x in cnt_total:
    #     cnt_total[x] -= cnt[x]
    # not_changes = 0
    # for i in range(3):
    #     for j in range(3):
    #         if i != j:
    #             not_changes = max(not_changes,cnt[i]+cnt_total[j])
    # changes = n*n - not_changes
    return changes


def weekly_contest_388_solution_1(apple: List[int], capacity: List[int]) -> int:
    sa = sum(apple)
    capacity.sort(reverse=True)
    cnt = 0
    while cnt < len(capacity) and sa > 0:
        sa -= capacity[cnt]
        cnt += 1
    return cnt


def weekly_contest_388_solution_2(happiness: List[int], k: int) -> int:
    happiness.sort(reverse=True)
    ans = 0
    cnt = 0
    while k > 0:
        ans += max(0, happiness[cnt] - cnt)
        cnt += 1
        k -= 1
    return ans


def weekly_contest_388_solution_3(arr: List[str]) -> List[str]:
    f = defaultdict(int)
    for s in arr:
        for i in range(1, len(s) + 1):
            for j in range(0, len(s) + 1 - i):
                f[s[j:j + i]] += 1
    ans = []
    for s in arr:
        tmp = []
        tf = defaultdict(int)
        for i in range(1, len(s) + 1):
            for j in range(0, len(s) + 1 - i):
                f[s[j:j + i]] -= 1
                tf[s[j:j + i]] += 1
        for c in tf:
            if f[c] == 0:
                tmp.append(c)
            f[c] += tf[c]
        tmp.sort(key=lambda x: (len(x), x))
        ans.append(tmp[0] if len(tmp) > 0 else "")
    return ans


def weekly_contest_388_solution_4(nums: List[int], k: int) -> int:
    """
    划分型 DP
    关键词: 划分,不相交

    1. 通常来说, f[i][j] 表示 前j个数分成i段
        对于本题,每段选一个子数组,对应最大能量值
    2. 不选num[j-1]: 问题变成 前j-1个数分成i段
        f[i][j-1] = f[i][j]
    3. 选num[j-1]: 考虑当前最后一个子数组的多种情况
        f[i][j] = max { f[i-1][L] + (s[j] - s[L]) * w }  # s前缀和
        L 最大值为 j-1
        L 最小值为 i-1
        w = (-1) ^ (i + 1) * (k - i + 1)
    4. 答案 = f[k][n]
        初始值f[0][j] = 0
             f[i][i-1(<i)] = -inf
    5. 暴力:
        枚举i(0...k),枚举j(0...n),枚举L(i-1...j-1)
        O(n*n*k)
    6. max_{L = i-1}^{j-1} { f[i-1][L] + (s[j] - s[L]) * w } 优化
    f[i][i] => 枚举 L= i-1
    f[i][i+1] => 枚举 L = i-1, i
    ...
        max_{L = i-1}^{j-1} { f[i-1][L] + (s[j] - s[L]) * w }
    =   max_{L = i-1}^{j-1} { f[i-1][L] + s[j]* w - s[L] * w }
    =   s[j]* w + max_{L = i-1}^{j-1} { f[i-1][L] - s[L] * w }

    f[i][j] => 枚举 L = (i-1, i, ..., j-1) 可以利用计算 f[i][j-1]的结果


    最终转移方程:
    f[i][j] = max(f[i][j-1], s[j]*w +mx)
    mx = max_{L = i-1}^{j-1} { f[i-1][L] - s[L] * w }
    """
    n = len(nums)
    s = list(accumulate(nums, initial=0))
    f = [[0] * (n + 1) for _ in range(k + 1)]
    for i in range(1, k + 1):
        f[i][i - 1] = mx = -inf
        w = (1 if i % 2 else -1) * (k - i + 1)
        for j in range(i, n - k + i + 1):  # 右侧要留下至少k-i个数字
            mx = max(mx, f[i - 1][j - 1] - s[j - 1] * w)
            f[i][j] = max(f[i][j - 1], s[j] * w + mx)
    return f[k][n]


def biweekly_contest_126_solution_1(nums: List[int]) -> int:
    ans = 0
    for num in nums:
        m = 0
        cnt = 0
        while num > 0:
            cnt += 1
            m = max(m, num % 10)
            num = num // 10
        cur = 0
        for i in range(cnt):
            cur = cur * 10 + m
        ans += cur
    return ans


def biweekly_contest_126_solution_1_2(nums: List[int]) -> int:
    ans = 0
    for s in map(str, nums):
        ans += int(max(s)) * int('1' * len(s))
    return ans


def biweekly_contest_126_solution_2(nums: List[int], queries: List[List[int]]) -> List[int]:
    total = sum(nums)
    h = []
    seen = set()
    for i, x in enumerate(nums):
        heapq.heappush(h, (x, i))
    ans = []
    for q in queries:
        cur = 0
        if q[0] not in seen:
            cur += nums[q[0]]
            seen.add(q[0])
        k = q[1]
        while k > 0 and h:
            x, idx = heapq.heappop(h)
            if idx in seen:
                continue
            else:
                seen.add(idx)
                cur += x
                k -= 1
        ans.append(total - cur)
        total = total - cur
    return ans


def biweekly_contest_126_solution_2_2(nums: List[int], queries: List[List[int]]):
    n = len(nums)
    ids = sorted(range(n), key=lambda i: nums[i])
    s = sum(nums)
    ans = []
    j = 0
    for i, k in queries:
        s -= nums[i]
        nums[i] = 0  # 标记　不需要判断ｉ是否标记过, -0对结果无影响
        while j < n and k:
            i = ids[j]
            if nums[i]:
                s -= nums[i]
                nums[i] = 0
                k -= 1
            j += 1
        ans.append(s)
    return ans


def biweekly_contest_126_solution_3(s: str) -> str:
    """
    cost 只和字母在ｓ中的出现次数有关
    基本不等式，分配的字母个数应该尽量接近
    假设有ｑ个问号，循环ｑ次
    每次把？改成出现次数最少的字母
    => 最小堆
    """
    freq = Counter[str](s)
    h = [(freq[c], c) for c in ascii_lowercase]
    heapq.heapify(h)
    t = []
    for _ in range(s.count('?')):
        f, c = h[0]
        t.append(c)
        heapq.heapreplace(h, (f + 1, c))  # 出现次数加１,压回堆
    t.sort()  # 需要字典序最小
    s = list(s)
    j = 0
    for i in range(len(s)):
        if s[i] == '?':
            s[i] = t[j]
            j += 1
    return ''.join(s)


def biweekly_contest_126_solution_4(nums: List[int], k: int) -> int:
    # 二维0-1背包
    # f[i][j][c]表示考虑前i个商品，所选物品体积为j,选了c个物品的方案数
    # f[i+1][j][c] = f[i][j][c] + f[i][j-nums[i]][c-1]
    # f[0][0][0] =1
    # ans = sum(f[n][k][c]*(2**(n-c))) c=1...n
    mod_factor = 10 ** 9 + 7
    n = len(nums)
    f = [[0] * (n + 1) for _ in range(k + 1)]
    f[0][0] = 1
    for i, x in enumerate(nums):
        for j in range(k, x - 1, -1):  # j<x时更新和不更新一样，没区别
            for c in range(i + 1, 0, -1):
                f[j][c] = (f[j][c] + f[j - x][c - 1]) % mod_factor
    ans = 0
    pow2 = 1
    for i in range(n, 0, -1):
        ans = (ans + f[k][i] * pow2) % mod_factor
        pow2 = pow2 * 2 % mod_factor
    return ans


def biweekly_contest_126_solution_4_2(nums: List[int], k: int) -> int:
    """
    贡献法

    假设和为ｋ的子序列ｓ的长度是ｃ
    那么ｓ会出现在　２^(n-c)　个包含ｓ的子序列中
    所以ｓ对答案的贡献就是２^(n-c)

    １. 二维0-1背包
    有ｎ个物品，每个物品的体积是nums[i]
    恰好装满容量为ｋ的背包，并且选的物品个数恰好是ｃ的方案数

    2. f[i][j] 表示考虑前i个数从中选出的子序列和为j时的能量和
    转移来源：
    1. f[i][j] = f[i-1][j] 子序列不含i
    2. f[i][j] = f[i-1][j]　子序列含i，但i不贡献到和中
    3. f[i][j] = f[i-1][j-nums[i-1]]

    f[i][j] = f[i-1]*2+f[i-1][j-nums[i-1]]
    f[0][0] = 1
    """
    mod_factor = 10 ** 9 + 7
    f = [1] + [0] * k
    for x in nums:
        for j in range(k, -1, -1):
            f[j] = (f[j] * 2 + (f[j - x] if j >= x else 0)) % mod_factor
    return f[k]


def weekly_contest_389_solution_1(s: str) -> bool:
    ss = set()
    for i in range(len(s) - 1):
        ss.add(s[i:i + 2])
    rs = s[::-1]
    for i in range(len(rs) - 1):
        if rs[i:i + 2] in ss:
            return True
    return False


def weekly_contest_389_solution_1_2(s: str) -> bool:
    st = set()
    for x, y in pairwise(s):
        st.add((x, y))
        if (y, x) in st:
            return True
    return False


def weekly_contest_389_solution_2(s: str, c: str) -> int:
    cnt = 0
    for x in s:
        if x == c:
            cnt += 1
    return (cnt + 1) * cnt // 2


def weekly_contest_389_solution_3(word: str, k: int) -> int:
    cnt = Counter[str](word)
    h = list(cnt.values())
    h.sort()
    ma = inf
    for i in range(len(h)):
        ans = sum(h[:i]) if i > 0 else 0
        mx = h[i]
        for j in range(len(h) - 1, i - 1, -1):
            if h[j] - mx > k:
                ans += h[j] - (mx + k)
            else:
                break
        ma = min(ans, ma)
    return ma


def weekly_contest_389_solution_3_2(word: str, k: int) -> int:
    """
    1. 求最多保留多少个字母
    2. 出现次数最多 - 出现次数最少　<= k
    3. 枚举出现次数最少的字母, base
        => c < base, 全部删除
        => c > base, 保留min(c,base+k)
    4. return len(word)-max_save
    """
    cnt = sorted(Counter[str](word).values())
    max_save = 0
    for i, base in enumerate(cnt):
        s = 0
        for c in cnt[i:]:
            s += min(c, base + k)
        max_save = max(max_save, s)
    return len(word) - max_save


def weekly_contest_389_solution_4(nums: List[int], k: int, maxChanges: int) -> int:
    """
    1. 当前位置的1, 操作0次
    2. 当前位置左右相邻位置的1, 操作1次
    3. 第一操作， 生成1个1, 第二种操作， 把这个1移动过来 => 操作2次
    4. 只用第二种操作，把在下标j的1,移动到当前下标index => abs(index-j)

    优先做哪些操作
    1. 先把index, index-1, index+1 这三个位置，至多3个1收集到
    2. 用第一种+第二种操作，得到maxChanges个1
    3. 如果还有需要得到的1,就用第二种操作


    1. 先把maxChanges较大的情况考虑了

    2. 如果只有操作2 => 货仓选址问题(中位数贪心)
    先把maxChanges个1,每个1用两次操作得到
    其余k-maxChanges个1,套用货仓选址问题解决

    先把nums中所有1的位置，保存到一个pos数组中
    pos的大小为k-maxChanges子数组的货仓选址问题
    """
    pos = []
    c = 0  # 统计最大的3位连续子数组中的1的个数
    for i, x in enumerate(nums):
        if x == 0:
            continue
        pos.append(i)  # 记录1的位置
        c = max(c, 1)
        if i > 0 and nums[i - 1] == 1:
            if i > 1 and nums[i - 2] == 1:
                c = 3  # 有3个连续的1
            else:
                c = max(c, 2)  # 有2个连续的1 用max防止3被2覆盖

    # maxChanges 较大
    c = min(c, k)
    if maxChanges >= k - c:
        return max(c - 1, 0) + (k - c) * 2

    n = len(pos)
    pre_sum = list(accumulate(pos, initial=0))
    ans = inf
    size = k - maxChanges
    for right in range(size, n + 1):
        # s1+s2 是j在[left, right)中的所有pos[j]到pos[left+right/2]的距离之和
        left = right - size
        i = left + size // 2
        s1 = pos[i] * (i - left) - (pre_sum[i] - pre_sum[left])
        s2 = pre_sum[right] - pre_sum[i] - pos[i] * (right - i)
        ans = min(ans, s1 + s2)
    return ans + maxChanges * 2


def weekly_contest_390_solution_1(s: str) -> int:
    cnt = defaultdict(int)
    l = 0
    for i in range(len(s)):
        flag = False
        for j in range(i, len(s)):
            if cnt[s[j]] == 2:
                flag = True
                break
            else:
                cnt[s[j]] += 1
        if flag:
            l = max(l, j - i)
        else:
            l = max(l, j - i + 1)
        cnt.clear()
    return l


def weekly_contest_390_solution_1_2(s: str) -> int:
    """
    O(n)
    滑动窗口
    """
    ans = left = 0
    cnt = Counter[str]()
    for i, c in enumerate(s):
        cnt[c] += 1
        # 窗口右移，直到没有字母cnt>2
        while cnt[c] > 2:
            cnt[s[left]] -= 1
            left += 1
        ans = max(ans, i - left + 1)
    return ans


def weekly_contest_390_solution_2(k: int) -> int:
    cnt = inf
    for i in range(1, k + 1):
        if k % i == 0:
            cur = (k // i) - 1 + (i - 1)
        else:
            cur = (k // i) + i - 1
        cnt = min(cur, cnt)
    return cnt


def weekly_contest_390_solution_3(nums: List[int], freq: List[int]) -> List[int]:
    """
    哈希表+有序集合(较复杂)
    """
    cnt = Counter[int]()
    d = SortedList()
    ans = []
    for x, f in zip(nums, freq):
        if cnt[x] in d:
            d.remove(cnt[x])
        cnt[x] += f
        d.add(cnt[x])
        ans.append(d[-1])
    return ans


def weekly_contest_390_solution_3_2(nums: List[int], freq: List[int]) -> List[int]:
    """
    哈希表+懒删堆
    """
    cnt = Counter[int]()
    h = []
    ans = []
    for x, f in zip(nums, freq):
        cnt[x] += f
        heapq.heappush(h, (-cnt[x], x))
        while cnt[h[0][1]] != -h[0][0]:
            heapq.heappop(h)
        ans.append(-h[0][0])
    return ans


def weekly_contest_390_solution_4(wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:
    t = Trie3093()
    for i, w in enumerate(wordsContainer):
        t.insert(w[::-1], i)
    ans = []
    for w in wordsQuery:
        ans.append(t.search(w[::-1]))
    return ans


def biweekly_contest_127_solution_1(nums: List[int], k: int) -> int:
    n = len(nums)
    cnt = inf
    for i in range(n):
        for j in range(i + 1, n + 1):
            ans = 0
            for m in range(i, j):
                ans |= nums[m]
            if ans >= k:
                cnt = min(cnt, j - i)
    return cnt if cnt < inf else -1


def biweekly_contest_127_solution_2(possible: List[int]) -> int:
    n = len(possible)
    pre = [0] * (n + 1)
    suf = [0] * (n + 1)
    for i, x in enumerate(possible):
        pre[i + 1] = pre[i] + (1 if x else -1)
    for i, x in enumerate(possible[::-1]):
        suf[i + 1] += suf[i] + (1 if x else -1)
    suf.reverse()
    for i in range(1, n):
        if pre[i] > suf[i]:
            return i
    return -1


def biweekly_contest_127_solution_2_2(possible: List[int]) -> int:
    # 每一项都是 s+=x*2-1
    s = sum(possible) * 2 - len(possible)
    pre = 0
    # suf[i]= total - pre[i]
    for i, x in enumerate(possible[:-1]):
        pre += x * 2 - 1
        if pre > s - pre:
            return i + 1
    return -1


def biweekly_contest_127_solution_3(nums: List[int], k: int) -> int:
    cnt = defaultdict(int)
    left = 0
    s = 0
    ans = inf
    for right in range(len(nums)):
        cur = nums[right]
        while cur > 0:
            lb = cur & (-cur)
            if cnt[lb] == 0:
                s += lb
            cnt[lb] += 1
            cur -= lb
        if s >= k:
            while left < right:
                l_cur = nums[left]
                cur_s = s
                while l_cur > 0:
                    lb = l_cur & (-l_cur)
                    if cnt[lb] == 1:
                        cur_s -= lb
                    l_cur -= lb
                if cur_s >= k:
                    l_cur = nums[left]
                    while l_cur > 0:
                        lb = l_cur & (-l_cur)
                        cnt[lb] -= 1
                        if cnt[lb] == 0:
                            s -= lb
                        l_cur -= lb
                    left += 1
                else:
                    break
            ans = min(ans, right - left + 1)
    return ans if ans < inf else -1


def biweekly_contest_127_solution_3_2(nums: List[int], k: int) -> int:
    """
    1. 枚举以i为右端点的子数组
    2. OR的性质：
    以i为右端点的子数组的OR，至多有O(log max(nums)) 个不同值

    从以i为右端点的子数组 到 以i+1为右端点的子数组
    增量式地计算子数组的OR
    维护子数组OR以及对应的子数组的左端点的最大值
    """
    # O(n*log max(nums))
    ans = inf
    d = dict()  # key 是 OR, value 是对应的子数组的左端点的最大值
    for i, x in enumerate(nums):
        d = {or_ | x: left for or_, left in d.items()}  # python按顺序存，从左到右遍历，刚好left最大的会保留
        d[x] = i
        for or_, left in d.items():
            if or_ >= k:
                ans = min(ans, i - left + 1)
    return ans if ans < inf else -1


def biweekly_contest_127_solution_4(nums: List[int], k: int) -> int:
    """
    子序列：
    相邻无关 0-1背包
    相邻相关 最长递增子序列

    递增子序列个数模板
    dfs(i,pre)
    不选 dfs(i-1,pre)
    选 dfs(i-1,nums[i])

    i是当前下标，j是还需要选多少个数
    pre是上一个选的数
    min_diff 是目前选的数的能量
    dfs(i,j,pre,min_diff)

    不选 dfs(i-1,j,pre,min_diff)
    选 dfs(i-1,j-1,nums[i],min(min_diff,pre-nums[i]))

    递归边界：
    j=0时 返回min_diff
    j>i+1时，即使全部选，也不足j个，返回0

    """
    MOD = 10 ** 9 + +7
    # 所有子序列的最小的绝对值差，因此顺序无关，可以排序来简化求最小的绝对值
    nums.sort()

    # 时间复杂度
    # 状态个数 * 单个状态的计算时间
    # i: n个
    # j: k个
    # pre: n个
    # min_diff:O(n^2)个
    # O(n^4k)
    @cache
    def dfs(i, j, pre, min_diff):
        if j > i + 1:
            return 0
        if j == 0:
            return min_diff
        res1 = dfs(i - 1, j, pre, min_diff)
        res2 = dfs(i - 1, j - 1, nums[i], min(min_diff, pre - nums[i]))
        return (res1 + res2) % MOD

    ans = dfs(len(nums) - 1, k, inf, inf)
    dfs.cache_clear()
    return ans


def weekly_contest_391_solution_1(x: int) -> int:
    s = str(x)
    ss = 0
    for c in s:
        c = ord(c) - ord("0")
        ss += c
    return ss if x % ss == 0 else -1


def weekly_contest_391_solution_2(numBottles: int, numExchange: int) -> int:
    cnt = 0
    full = numBottles
    while True:
        cnt += full
        if numBottles >= numExchange:
            numBottles = numBottles - numExchange + 1
            numExchange += 1
            full = 1
        else:
            return cnt


def weekly_contest_391_solution_3(nums: List[int]) -> int:
    idx = []
    left = 0
    for right in range(1, len(nums)):
        if nums[right] == nums[right - 1]:
            idx.append((left, right - 1))
            left = right
    idx.append((left, len(nums) - 1))
    ans = 0
    for l, r in idx:
        length = r - l + 1
        ans += ((length + 1) * length) // 2
    return ans


def weekly_contest_391_solution_4(points: List[List[int]]) -> int:
    """
    (x1, y1), (x2, y2)
    dist = |x1 - x2| + |y1 - y2|

    曼哈顿距离与切比雪夫距离关系
    |x1 - x2| + |y1 - y2| = max(|x1'-x2'|,|y1'-y2'|)

    x' = x+y
    y' = y-x

    优化，可以只维护最大最小次大次小x和y，共8个值
    """
    xs = SortedList()
    ys = SortedList()
    for x, y in points:
        xs.add(x + y)
        ys.add(y - x)
    ans = inf
    for x, y in points:
        x, y = x + y, y - x
        xs.remove(x)
        ys.remove(y)
        ans = min(ans, max(xs[-1] - xs[0], ys[-1] - ys[0]))
        xs.add(x)
        ys.add(y)
    return ans


def weekly_contest_392_solution_1(nums: List[int]) -> int:
    ans = 1
    n = len(nums)
    for i in range(n):
        cur = 1
        for j in range(i, n - 1):
            if nums[j] > nums[j + 1]:
                cur += 1
            else:
                break
        ans = max(cur, ans)
        cur = 1
        for j in range(i, n - 1):
            if nums[j] < nums[j + 1]:
                cur += 1
            else:
                break
        ans = max(cur, ans)
    return ans


def weekly_contest_392_solution_1_2(nums: List[int]) -> int:
    # 分组循环
    ans = 1
    n = len(nums)
    i = 0
    while i < n - 1:
        if nums[i + 1] == nums[i]:
            i += 1
            continue
        i0 = i
        inc = nums[i + 1] > nums[i]
        i += 2
        # 同时判断递增递减
        while i < n and nums[i] != nums[i - 1] and (nums[i] > nums[i - 1]) == inc:
            i += 1
        ans = max(ans, i - i0)  # i0 - i-1 满足要求
        i -= 1  # 恢复i0
    return ans


def weekly_contest_392_solution_2(s: str, k: int) -> str:
    ans = list(s)
    for i, c in enumerate(ans):
        dist = ord(c) - ord('a')
        dist = min(dist, 26 - dist)
        if dist <= k:
            ans[i] = 'a'
            k -= dist
        else:
            ans[i] = chr(ord(c) - k)
            break
    return "".join(ans)


def weekly_contest_392_solution_3(nums: List[int], k: int) -> int:
    nums.sort()
    mid = len(nums) // 2
    ans = abs(nums[mid] - k)
    nums[mid] = k
    for i in range(mid - 1, -1, -1):
        if nums[i] > k:
            ans += nums[i] - k
        else:
            break
    for i in range(mid + 1, len(nums)):
        if nums[i] < k:
            ans += k - nums[i]
        else:
            break
    return ans


def weekly_contest_392_solution_4(n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
    g = [[] for _ in range(n)]
    for u, v, w in edges:
        g[u].append((v, w))
        g[v].append((u, w))

    def dfs(x, ms):
        nonlocal cost
        for y, _ in g[x]:
            if y not in ms:
                ms.add(y)
                dfs(y, ms)

    groups = []
    for i in range(n):
        flag = False
        for gr, _ in groups:
            if i in gr:
                flag = True
                break
        if flag:
            continue
        ss = set()
        ss.add(i)
        cost = -1
        dfs(i, ss)
        for x in ss:
            for y, w in g[x]:
                cost &= w
        groups.append((ss, cost))
    ans = []
    for u, v in query:
        if u == v:
            ans.append(0)
            continue
        flag = False
        for gr, cost in groups:
            if u in gr and v in gr:
                ans.append(cost)
                flag = True
                break
        if not flag:
            ans.append(-1)
    return ans


def weekly_contest_392_solution_4_2(n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
    """
    并查集优化
    """
    fa = list(range(n))
    and_ = [-1] * n

    def find(x: int) -> int:
        if fa[x] != x:
            fa[x] = find(fa[x])
        return fa[x]

    for x, y, w in edges:
        x = find(x)
        y = find(y)
        and_[y] &= w
        if x != y:
            and_[y] &= and_[x]
            fa[x] = y

    return [0 if s == t else -1 if find(s) != find(t) else and_[find(s)] for s, t in query]


def biweekly_contest_128_solution_1(s: str) -> int:
    ans = 0
    for i in range(len(s) - 1):
        ans += abs(ord(s[i]) - ord(s[i + 1]))
    return ans


def biweekly_contest_128_solution_2(points: List[List[int]], w: int) -> int:
    points.sort(key=lambda x: x[0])
    cnt = 0
    last = -w - 1
    for x, _ in points:
        if last + w < x:
            cnt += 1
            last = x
    return cnt


def biweekly_contest_128_solution_3(n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
    # 堆优化 Dijkstra（适用于稀疏图）
    # 开太大了
    # 如果开g[n][n] 无效遍历太多
    g = [[] * n for _ in range(n)]
    for x, y, d in edges:
        g[x].append((y, d))
        g[y].append((x, d))
    dist = [-1] * n
    dist[0] = 0
    h = [(dist[0], 0)]  # 注意元组大小比较顺序
    while h:
        dx, x = heapq.heappop(h)
        if dx > dist[x]:
            continue
        for (y, d) in g[x]:
            new_dis = dx + d
            if (dist[y] < 0 or new_dis < dist[y]) and new_dis < disappear[y]:
                dist[y] = new_dis
                heapq.heappush(h, (new_dis, y))
    return dist


def biweekly_contest_128_solution_4(nums: List[int]) -> int:
    """
    子数组问题： 通用的思考方式
    枚举右端点
    """
    ans = len(nums)  # 长度为1的单独处理
    st = [[inf, inf]]
    for x in nums:
        while x > st[-1][0]:
            st.pop()
        if x == st[-1][0]:
            ans += st[-1][1]  # 当前可以与右端点组成子数组的个数
            st[-1][1] += 1
        else:
            st.append([x, 1])
    return ans


def weekly_contest_393_solution_1(s: str) -> str:
    ls = list(s)
    if ls[0] == '?':
        if ls[1] == '1' or ls[1] == '?' or ls[1] == '0':
            ls[0] = '1'
        else:
            ls[0] = '0'
    if ls[1] == '?':
        if ls[0] == '1':
            ls[1] = '1'
        else:
            ls[1] = '9'
    if ls[3] == '?':
        ls[3] = '5'
    if ls[4] == '?':
        ls[4] = '9'
    return ''.join(ls)


def weekly_contest_393_solution_1_2(s: str) -> str:
    # 暴力
    for h in range(11, -1, -1):
        for m in range(59, -1, -1):
            t = f'{h:02d}:{m:02d}'
            # for x, y in zip(s, t):
            #     if x != '?' and x != y:
            #         break
            # else:
            #     return t
            if all(x == '?' or x == y for x, y in zip(s, t)):
                return t


def weekly_contest_393_solution_2(nums: List[int]) -> int:
    def sieve_of_eratosthenes(n):
        ans = set()
        prime = [True] * (n + 1)
        prime[0] = prime[1] = False
        for i in range(2, n + 1):
            if prime[i]:
                ans.add(i)
            for num in range(i * 2, n + 1, i):
                prime[num] = False
        return ans

    primes = sieve_of_eratosthenes(100)
    # sl = SortedList()
    # for i, x in enumerate(nums):
    #     if x in primes:
    #         sl.add(i)
    # return sl[-1] - sl[0]
    i = 0
    while not nums[i] in primes:
        i += 1
    j = len(nums) - 1
    while not nums[j] in primes:
        j -= 1
    return j - i


def weekly_contest_393_solution_3(coins: List[int], k: int) -> int:
    """
    二分：
    统计有多少个金额 <= m
    """
    n = len(coins)

    # 枚举子集
    def check(m: int) -> bool:
        cnt = 0
        for i in range(1, 1 << n):  # 二进制枚举所有子集
            lcm_res = 1
            for j, x in enumerate(coins):
                if i >> j & 1:  # 当前硬币在当前子集中
                    lcm_res = math.lcm(lcm_res, x)
            c = m // lcm_res  # 集合i对cnt的贡献
            cnt += c if i.bit_count() % 2 else -c
        return cnt >= k

    left = k - 1  # 一定不满足要求
    right = min(coins) * k  # 一定满足要求
    while left + 1 < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid
    return right


def weekly_contest_393_solution_4(nums: List[int], andValues: List[int]) -> int:
    """
    所有子数组 O(n^2) 只有 O(nlogU) U=max(nums) 个不同的与值

    i 表示从nums[i]开始往后的后缀
    j 表示已经划分的子数组个数
    and 表示当前这一段的已经遍历过的元素的 AND
    dfs(i, j, and)
    1. 不划分: dfs(i+1, j, and)
    2. 划分： dfs(i+1,j+1,-1) + nums[i] #最后一个数的值
    划分的要求： and = andValues[i]

    两种情况取min， 即为dfs(i,j,and)
    """
    n = len(nums)
    m = len(andValues)

    # O(n * m * logU)
    @cache
    def dfs(i: int, j: int, nd: int) -> int:
        if i == n:
            return 0 if j == m else inf
        if j == m:
            return inf
        nd &= nums[i]
        if nd < andValues[j]:  # 剪枝
            return inf
        res = dfs(i + 1, j, nd)
        if nd == andValues[j]:
            res = min(res, dfs(i + 1, j + 1, -1) + nums[i])
        return res

    ans = dfs(0, 0, -1)
    return ans if ans < inf else -1


def weekly_contest_394_solution_1(word: str) -> int:
    cnt = set(word)
    ans = 0
    for i in range(0, 26):
        c = chr(ord('a') + i)
        if c in cnt and c.upper() in cnt:
            ans += 1
    return ans


def weekly_contest_394_solution_1_2(word: str) -> int:
    """
    1. ASCII >> 5 & 1 判定是大写还是小写
    2. ASCII & 31 取出这个字母是第几个字母
    """
    mask = [0, 0]
    for c in map(ord, word):
        mask[c >> 5 & 1] |= 1 << (c & 31)
    return (mask[0] & mask[1]).bit_count()


def weekly_contest_394_solution_2(word: str) -> int:
    cnt = [[-1] * 26, [-1] * 26]
    for i, c in enumerate(word):
        if c.islower():
            n = ord(c) - ord('a')
            cnt[0][n] = i
    for i in range(len(word) - 1, -1, -1):
        c = word[i]
        if c.isupper():
            n = ord(c) - ord('A')
            cnt[1][n] = i
    ans = 0
    for i in range(26):
        if cnt[1][i] != -1 and cnt[0][i] != -1 and cnt[1][i] > cnt[0][i]:
            ans += 1
    return ans


def weekly_contest_394_solution_2_2(word: str) -> int:
    """
    状态机
    """
    ans = 0
    state = [0] * 27
    for c in word:
        x = ord(c) & 31
        if c.islower():
            if state[x] == 0:  # 接受小写，进入状态1
                state[x] = 1
            elif state[x] == 2:  # 接受小写，进入黑洞
                state[x] = -1
                ans -= 1
        else:
            if state[x] == 0:  # 接受大写，进入状态1
                state[x] = -1
            elif state[x] == 1:
                state[x] = 2  # 接受大写，进入状态2
                ans += 1
    return ans


def weekly_contest_394_solution_3(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    cnt = []
    for j in range(n):
        tmp = Counter[int]()
        for i in range(m):
            tmp[grid[i][j]] += 1
        cnt.append(tmp)

    @cache
    def dfs(j: int, last: int) -> int:
        if j == n:
            return 0
        res = 0
        for i in range(10):
            if i != last:
                res = max(res, cnt[j][i] + dfs(j + 1, i))
        return res

    return n * m - dfs(0, -1)


def weekly_contest_394_solution_4(n: int, edges: List[List[int]]) -> List[bool]:
    # 堆优化 Dijkstra（适用于稀疏图）
    # 开太大了
    # 如果开g[n][n] 无效遍历太多
    g = [[] * n for _ in range(n)]
    for i, (x, y, d) in enumerate(edges):
        g[x].append((y, d, i))
        g[y].append((x, d, i))
    dist = [-1] * n
    _in = [set() for _ in range(n)]
    dist[0] = 0
    h = [(dist[0], 0)]  # 注意元组大小比较顺序
    while h:
        dx, x = heapq.heappop(h)
        if dx > dist[x]:
            continue
        for (y, d, i) in g[x]:
            new_dis = dx + d
            if dist[y] < 0 or new_dis < dist[y]:
                dist[y] = new_dis
                _in[y] = _in[x].copy()
                _in[y].add(i)
                heapq.heappush(h, (new_dis, y))
            elif new_dis == dist[y]:
                _in[y] = _in[y].copy() | _in[x].copy()
                _in[y].add(i)
                heapq.heappush(h, (new_dis, y))
    ans = [False] * len(edges)
    for i in range(len(edges)):
        if i in _in[n - 1]:
            ans[i] = True
    return ans


def biweekly_contest_129_solution_1(grid: List[List[str]]) -> bool:
    for i in range(len(grid) - 1):
        for j in range(len(grid[0]) - 1):
            cnt = 0
            if grid[i][j] == 'W':
                cnt += 1
            if grid[i + 1][j] == 'W':
                cnt += 1
            if grid[i][j + 1] == 'W':
                cnt += 1
            if grid[i + 1][j + 1] == 'W':
                cnt += 1
            if cnt >= 3 or cnt <= 1:
                return True
    return False


def biweekly_contest_129_solution_2(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    cnt_r = [0] * m
    cnt_c = [0] * n
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                cnt_r[i] += 1
                cnt_c[j] += 1
    ans = 0
    for i in range(m):
        if cnt_r[i] <= 1:
            continue
        for j in range(n):
            if grid[i][j] == 1 and cnt_r[i] > 1 and cnt_c[j] > 1:
                ans += (cnt_r[i] - 1) * (cnt_c[j] - 1)
    return ans


def biweekly_contest_129_solution_3(zero: int, one: int, limit: int) -> int:
    return biweekly_contest_129_solution_4(zero, one, limit)


def biweekly_contest_129_solution_4(zero: int, one: int, limit: int) -> int:
    """
    limit: 最多有连续limit个0和连续limit个1

    dfs(i,j,k): 表示用i个0，j个1，且第i+j个位置要填k

    k=0

    dfs(i,j,0) <- dfs(i-1,j,1) + dfs(i-1,j,0) - dfs(i-limit-1,j,1)

    dfs(i-limit-1,j,1) 这里是后继全0导致现在超过limit个0的方案数，所以减去

    dfs(i,j,1) <- dfs(i,j-1,1) + dfs(i,j-1,0) - dfs(i,j-limit-1,1)

    """
    mod_factor = 10 ** 9 + 7

    @cache
    def dfs(i: int, j: int, k: int) -> int:
        if i == 0:
            return 1 if k == 1 and j <= limit else 0
        if j == 0:
            return 1 if k == 0 and i <= limit else 0
        if k == 0:
            return (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - (dfs(i - limit - 1, j, 1) if i > limit else 0)) % mod_factor
        else:
            return (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - (dfs(i, j - limit - 1, 0) if j > limit else 0)) % mod_factor

    ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod_factor
    dfs.cache_clear()
    return ans


def weekly_contest_395_solution_1(nums1: List[int], nums2: List[int]) -> int:
    nums1.sort()
    nums2.sort()
    ans = nums2[0] - nums1[0]
    return ans


def weekly_contest_395_solution_2(nums1: List[int], nums2: List[int]) -> int:
    nums1.sort()
    nums2.sort()
    for x in range(-1000, 1001):
        cnt = 0
        flag = False
        for i in range(len(nums1)):
            if i - cnt >= len(nums2):
                break
            if nums1[i] + x == nums2[i - cnt]:
                continue
            else:
                cnt += 1
                if cnt > 2:
                    flag = True
                    break
        if not flag:
            return x


def weekly_contest_395_solution_2_2(nums1: List[int], nums2: List[int]) -> int:
    """
    答案只可能是排序后
    num2[0]-num1[0] > num2[0]-num1[1] > num2[0]-num1[2]
    """
    nums1.sort()
    nums2.sort()
    for i in range(2, -1, -1):
        diff = nums2[0] - nums1[i]
        j = 0
        # 从nums[i]开始遍历，就不需要考虑删除几个元素了，只需要确保nums2-diff是nums1 子序列就行
        for v in nums1[i:]:
            if j < len(nums2) and nums2[j] - v == diff:
                j += 1
                if j == len(nums2):
                    return diff


def weekly_contest_395_solution_3(n: int, x: int) -> int:
    # mask = x
    # last = x
    # for i in range(n - 1):
    #     cur = last
    #     while cur == last:
    #         cur = (cur + 1) | mask
    #     last = cur
    # return last
    t = x
    mask = x
    bits = [0] * 64
    nums = [0] * 64
    i = 0
    while x > 0:
        cur = x & 1
        x >>= 1
        bits[i] = cur
        i += 1
    cur = 0
    last = 0
    n = n - 1
    if n == 0:
        return t
    for i in range(64):
        if bits[i] == 0:
            nums[i] = 2 ** cur + last
            if nums[i] >= n:
                # ans
                ans = mask | (1 << i)
                res = n - last - 1
                idx = 0
                while res > 0:
                    tmp = res & 1
                    while bits[idx] != 0:
                        idx += 1
                    ans |= tmp << idx
                    idx += 1
                    res >>= 1
                return ans
            last = nums[i]
            cur += 1


def weekly_contest_395_solution_3_2(n: int, x: int) -> int:
    """
    直接填出第n-1个数
    """
    n -= 1
    i = j = 0
    ans = x
    while n >> j:
        if not x >> i & 1:
            b = n >> j & 1
            ans |= b << i
            j += 1
        i += 1
    return ans


def weekly_contest_395_solution_3_3(n: int, x: int) -> int:
    """
    low bit + 异或 + 取反
    """
    t = ~x
    n -= 1
    j = 0
    ans = x
    while n >> j:
        lb = t & -t
        b = n >> j & 1
        ans |= b * lb  # 乘法相当if else, lb来表示位置
        j += 1
        t = t ^ lb
    return ans


def weekly_contest_395_solution_4(nums: List[int]) -> int:
    n = len(nums)
    k = (n * (n + 1) // 2 + 1) // 2

    def check(x):
        cnt = l = 0
        freq = Counter()
        for r, in_ in enumerate(nums):
            freq[in_] += 1
            while len(freq) > x:
                out = nums[l]
                freq[out] -= 1
                if freq[out] == 0:
                    del freq[out]
                l += 1
            cnt += r - l + 1
            if cnt >= k:
                return True
        return False

    left = 0
    right = len(set(nums))
    while left + 1 < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid
    return right


def weekly_contest_396_solution_1(word: str) -> bool:
    if len(word) < 3:
        return False
    if '@' in word or '#' in word or '$' in word:
        return False
    word = word.lower()
    w = set(word)
    if 'a' in w or 'e' in w or 'i' in w or 'o' in w or 'u' in w:
        w = w - {'a', 'e', 'i', 'o', 'u'}
        w = w - {'1', '2', '3', '4', '5', '6', '7', '8', '9', '0'}
        if len(w) > 0:
            return True
    return False


def weekly_contest_396_solution_2(word: str, k: int) -> int:
    n = len(word)
    f = {}
    for i in range(0, n, k):
        t = word[i:i + k]
        if t not in f:
            f[t] = 1
        else:
            f[t] += 1
    mx = 0
    for t in f:
        if f[t] > mx:
            mx = f[t]
    return (n // k) - mx


def weekly_contest_396_solution_3(s: str) -> int:
    n = ans = len(s)
    cnt = Counter[str](s)
    mn = min(cnt.values())
    for i in range(1, mn + 1):
        if mn % i != 0:
            continue
        k = mn // i  # 组数
        for c in cnt:
            if cnt[c] % k != 0:
                break
        else:
            step = n // k  # 每组的长度
            flag = True
            for j in range(0, n, step):
                cnt1 = Counter[str](s[j:j + step])
                for c in cnt:
                    if c not in cnt1 or cnt[c] // k != cnt1[c]:
                        flag = False
                        break
                if not flag:
                    break
            if flag:
                return n // k
    return ans


def weekly_contest_396_solution_4(nums: List[int], cost1: int, cost2: int) -> int:
    """
    TLE
    1. 枚举最终所有数都变成x,总共增加s次值

    case1: 如果 c1*2 <= c2, 全用操作1
        cost = s * c1
    case2: 如果 c1*2 >  c2, 全用操作1
        d = x - min(nums)
        case 2-1: d <= s-d  能确保尽可能多的使用c2而不会违反规则
            cost = s // 2 * c2 + s % 2 * c1
        case 2-1: d > s-d
            cost = (s - d) * c2 + (d * 2 - s) * c1

    """
    mod_factor = 10 ** 9 + 7
    n = len(nums)
    mn = min(nums)
    mx = max(nums)

    # 所有数都变成max的增加次数

    s = mx * n - sum(nums)
    if cost1 * 2 <= cost2:
        return s * cost1 % mod_factor
    ans = inf
    for x in range(mx, mx * 2 + 1):
        d = x - mn
        # 当x增大时，d <= s-d 越可能成立，继续枚举更大的x，不会得到更小的答案
        if d <= s - d:
            res = s // 2 * cost2 + s % 2 * cost1
        else:
            res = (s - d) * cost2 + (d * 2 - s) * cost1
        ans = min(ans, res)  # 很慢
        s += n

    return ans % mod_factor


def weekly_contest_396_solution_4_2(nums: List[int], cost1: int, cost2: int) -> int:
    """
    1. 枚举最终所有数都变成x,总共增加s次值

    case1: 如果 c1*2 <= c2, 全用操作1
        cost = s * c1
    case2: 如果 c1*2 >  c2, 全用操作1
        d = x - min(nums)
        case 2-1: d <= s-d  能确保尽可能多的使用c2而不会违反规则
            cost = s // 2 * c2 + s % 2 * c1
        case 2-1: d > s-d
            cost = (s - d) * c2 + (d * 2 - s) * c1

    2. 二分
        base = mx * n - sum(nums)
        s = base + (x - mx) *n
        s = x*n - sum(nums)
        case 2-1:
            y = (x*n - sum(nums)) / 2 * c2 + ((x*n - sum(nums)) % 2) * c1
            dy / dx = n * c2 / 2 + o(...)
        case 2-2:
            y = (s - d) * c2 + (d * 2 - s) * c1
              = (c2 - c1) * s + (2 * c1 - c2) * d
              = (c2 - c1) * (x * n - sum(nums)) + (2 * c1 - c2) * (x - min(nums))
            dy / dx = (c2 - c1) * n + 2 * c1 - c2

        case2 单峰函数 -> 三分法 二分斜率
        二分导数的0值
        对于本题，二分找第一个满足y(m) < y(m+1) 的m
    """
    mod_factor = 10 ** 9 + 7
    n = len(nums)
    mn = min(nums)
    mx = max(nums)
    base = mx * n - sum(nums)
    if cost1 * 2 <= cost2:
        return base * cost1 % mod_factor

    def f(x: int) -> int:
        s = base + (x - mx) * n
        d = x - mn
        if d <= s - d:
            return s // 2 * cost2 + s % 2 * cost1
        return (s - d) * cost2 + (d * 2 - s) * cost1

    ans = inf
    if mx % 2:
        ans = f(mx)
        mx += 1
        base += n

    # 奇偶不同情况下的二分
    k0 = bisect_left(range(mx), True, mx // 2, key=lambda m: f(m * 2) < f((m + 1) * 2))
    k1 = bisect_left(range(mx), True, mx // 2, key=lambda m: f(m * 2 + 1) < f((m + 1) * 2 + 1))
    ans = min(ans, f(k0 * 2), f(k1 * 2 + 1))
    return ans % mod_factor


def b130_1(grid: List[List[int]]) -> bool:
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if i == len(grid) - 1 and j == len(grid[0]) - 1:
                continue
            if i == len(grid) - 1:
                if grid[i][j] != grid[i][j + 1]:
                    continue
                else:
                    return False
            if j == len(grid[0]) - 1:
                if grid[i][j] == grid[i + 1][j]:
                    continue
                else:
                    return False
            if grid[i][j] == grid[i + 1][j] and grid[i][j] != grid[i][j + 1]:
                continue
            return False
    return True


def b130_1_2(grid: List[List[int]]) -> bool:
    for i, row in enumerate(grid):
        for j, x in enumerate(row):
            if j and x == row[j - 1] or i and x != grid[i - 1][j]:
                return False
    return True


def b130_2(points: List[List[int]], s: str) -> int:
    dist = [0] * len(s)
    for i in range(len(points)):
        dist[i] = max(abs(points[i][0]), abs(points[i][1])) * 2
    p = sorted(zip(dist, s), key=lambda x: x[0])
    seen = set()
    ans = 0
    cur = 0
    cur_cnt = 0
    for x, l in p:
        if l in seen:
            if x == cur:
                ans -= cur_cnt
                return ans
            else:
                return ans
        else:
            seen.add(l)
            ans += 1
            if cur == x:
                cur_cnt += 1
            else:
                cur = x
                cur_cnt = 1
    return ans


def b130_2_2(points: List[List[int]], s: str) -> int:
    # 维护次小距离的最小值
    min_d = defaultdict(lambda: inf)
    min2 = inf
    for (x, y), c in zip(points, s):
        d = max(abs(x), abs(y))
        if d < min_d[c]:
            # d是目前最小的,那么min_d 是次小的
            min2 = min(min2, min_d[c])
            min_d[c] = d
        else:
            min2 = min(min2, d)
    # min2 是不合法距离
    return sum(d < min2 for d in min_d.values())


def b130_2_3(points: List[List[int]], s: str) -> int:
    # 二分找正方形边长
    ans = 0

    def check(size: int) -> bool:
        vis = set()
        for (x, y), c in zip(points, s):
            if abs(x) <= size and abs(y) <= size:
                if c in vis:
                    return True
                vis.add(c)
        nonlocal ans  # 记录答案
        ans = len(vis)
        return False

    # 最后一个True不会影响ans的值
    bisect_left(range(10 ** 9 + 1), True, key=check)
    return ans


def b130_3(s: str) -> int:
    @cache
    def dfs(i: int) -> int:
        if i < 0:
            return 0
        res = inf
        cnt = defaultdict(int)
        max_cnt = 0
        for j in range(i, -1, -1):
            cnt[s[j]] += 1
            max_cnt = max(max_cnt, cnt[s[j]])
            # 不满足这个条件,不是合法转移
            if i - j + 1 == len(cnt) * max_cnt:
                res = min(res, dfs(j - 1) + 1)
        return res

    return dfs(len(s) - 1)


def b130_4(queries: List[List[int]]) -> List[int]:
    """
    直接上链接吧，太复杂了
    https://leetcode.cn/problems/find-products-of-elements-of-big-array/solutions/2774549/olog-shi-tian-fa-pythonjavacgo-by-endles-w2l4/
    https://www.bilibili.com/video/BV1cz421m786/
    """

    def sum_e(k: int) -> int:
        res = n = cnt1 = sum_i = 0
        for i in range((k + 1).bit_length() - 1, 0, -1):
            c = (cnt1 << i) + (i << (i - 1))  # 新增的幂次个数
            if c <= k:
                k -= c
                res += (sum_i << i) + ((i * (i - 1) // 2) << (i - 1))
                sum_i += i  # 之前填的1的幂次之和
                cnt1 += 1  # 之前填的1的个数
                n |= 1 << i  # 填1
        # 最低位单独计算
        if cnt1 <= k:
            k -= cnt1
            res += sum_i
            n += 1
        # 剩余的 k 个幂次，由 n 的低 k 个 1 补充
        for _ in range(k):
            lb = n & -n
            res += lb.bit_length() - 1
            n ^= lb
        return res

    return [pow(2, sum_e(r + 1) - sum_e(l), mod) for l, r, mod in queries]


def w397_1(s: str, t: str) -> int:
    f = defaultdict(int)
    g = defaultdict(int)
    for i in range(len(s)):
        f[s[i]] = i
        g[t[i]] = i
    ans = 0
    for c in f:
        ans += abs(f[c] - g[c])
    return ans


def w397_2(energy: List[int], k: int) -> int:
    ans = -inf
    for i in range(k):
        m = -inf
        tmp = 0
        for j in range(len(energy) - 1 - i, -1, -k):
            tmp += energy[j]
            if tmp > m:
                m = tmp
        ans = max(ans, m)
    return ans


def w397_3(grid: List[List[int]]) -> int:
    @cache
    def dfs(i, j):
        if i == len(grid) - 1 and j == len(grid[0]) - 1:
            return 0
        elif i == len(grid) - 1:
            return max(0, dfs(i, j + 1) + grid[i][j + 1] - grid[i][j])
        elif j == len(grid[0]) - 1:
            return max(0, dfs(i + 1, j) + grid[i + 1][j] - grid[i][j])
        else:
            return max(0, dfs(i + 1, j) + grid[i + 1][j] - grid[i][j], dfs(i, j + 1) + grid[i][j + 1] - grid[i][j])

    ans = -inf
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if i == len(grid) - 1 and j == len(grid[0]) - 1:
                continue
            elif i == len(grid) - 1:
                tmp = dfs(i, j + 1) + grid[i][j + 1] - grid[i][j]
            elif j == len(grid[0]) - 1:
                tmp = dfs(i + 1, j) + grid[i + 1][j] - grid[i][j]
            else:
                tmp = max(dfs(i + 1, j) + grid[i + 1][j] - grid[i][j], dfs(i, j + 1) + grid[i][j + 1] - grid[i][j])
            if tmp > ans:
                ans = tmp
    dfs.cache_clear()
    return ans


def w397_3_2(grid: List[List[int]]) -> int:
    """
    grid[i][j]视为海拔高度，要计算的是重力势能的变化之和，也就是终点和起点的海拔高度之差
    类似二维前缀和
    """
    ans = -inf
    m, n = len(grid), len(grid[0])
    f = [[inf] * (n + 1) for _ in range(m + 1)]
    for i, row in enumerate(grid):
        for j, x in enumerate(row):
            mn = min(f[i + 1][j], f[i][j + 1])
            ans = max(ans, x - mn)
            f[i + 1][j + 1] = min(mn, x)
    return ans


def w397_4(nums: List[int]) -> List[int]:
    """
    排列循环左移不会导致分数变化
    推论： 题目要计算的字典序最小的排列p，一定满足p0=0

    枚举选哪个

    dfs(S,j) 之前选过的数集合为S，上一个选的数是j的情况下，剩余数字能得到的最低分数

    dfs(S,j) = min dfs( S | {k}, k) + |j - ak|
    """
    n = len(nums)

    @cache
    def dfs(s: int, j: int) -> int:
        if s == (1 << n) - 1:
            # 所有位置都填完了，最后一个位置下标是j。计算分数
            return abs(j - nums[0])
        res = inf
        for k in range(1, n):
            if s >> k & 1 == 0:
                res = min(res, dfs(s | 1 << k, k) + abs(j - nums[k]))
        return res

    ans = []

    # 先计算完最优结果, 然后重新构造ans
    def make_ans(s: int, j: int) -> None:
        ans.append(j)
        if s == (1 << n) - 1:
            return
        final_res = dfs(s, j)
        for k in range(1, n):
            if s >> k & 1 == 0 and dfs(s | 1 << k, k) + abs(j - nums[k]) == final_res:
                make_ans(s | 1 << k, k)
                break  # 保证只有一条链

    make_ans(1, 0)
    return ans


def w398_1(nums: List[int]) -> bool:
    # if len(nums) == 1:
    #     return True
    # for x, y in pairwise(nums):
    #     if x % 2 == 0 and y % 2 == 1 or x % 2 == 1 and y % 2 == 0:
    #         continue
    #     else:
    #         return False
    # return True
    return all(x % 2 != y % 2 for x, y in pairwise(nums))


def w398_2(nums: List[int], queries: List[List[int]]) -> List[bool]:
    # x^y^1 即 x和y的奇偶相反
    if len(nums) == 1:
        return [True] * len(queries)
    bs = []
    for x, y in pairwise(nums):
        if x % 2 == 0 and y % 2 == 1 or x % 2 == 1 and y % 2 == 0:
            bs.append(1)
        else:
            bs.append(0)
    s = list(accumulate(bs, initial=0))
    ans = [False] * len(queries)
    for i, (left, right) in enumerate(queries):
        t = s[right] - s[left]
        if t != right - left:
            ans[i] = False
        else:
            ans[i] = True
    return ans


def w398_3(nums: List[int]) -> int:
    size = len(str(nums[0]))
    cnt = [Counter[int]() for _ in range(size)]
    for num in nums:
        i = 0
        while num > 0:
            t = num % 10
            cnt[i][t] += 1
            num //= 10
            i += 1
    ans = 0
    for cnt0 in cnt:
        for c in cnt0:
            ans += (cnt0[c] * (cnt0.total() - cnt0[c]))
    return ans // 2


def w398_4(k: int) -> int:
    @cache
    def dfs(i, jump, f):
        if i > k + f:
            return 0
        res = 1 if i == k else 0
        res += dfs(i + (1 << jump), jump + 1, 1)
        if f == 1 and i != 0:
            res += dfs(i - 1, jump, 0)
        return res

    return dfs(1, 0, 1)


def w398_4_2(k: int) -> int:
    ans = 0
    for j in range(30):
        m = (1 << j) - k
        if 0 <= m <= j + 1:
            ans += math.comb(j + 1, m)
    return ans


def b131_1(nums: List[int]) -> int:
    # nums[i]<=50
    ans = vis = 0
    for x in nums:
        if vis >> x & 1:
            ans ^= x
        else:
            vis |= 1 << x
    return ans


def b131_2(nums: List[int], queries: List[int], x: int) -> List[int]:
    # f = []
    # for i, num in enumerate(nums):
    #     if num != x:
    #         continue
    #     f.append(i)
    # ans = [-1] * len(queries)
    # for i, q in enumerate(queries):
    #     if q > len(f):
    #         continue
    #     ans[i] = f[q - 1]
    # return ans
    pos = [i for i, v in enumerate(nums) if v == x]
    return [-1 if q > len(pos) else pos[q - 1] for q in queries]


def b131_3(limit: int, queries: List[List[int]]) -> List[int]:
    f = defaultdict(int)
    seen = defaultdict(int)
    cnt = 0
    ans = [0] * len(queries)
    for i, q in enumerate(queries):
        idx, color = q
        if f[idx] != 0:
            seen[f[idx]] -= 1
            if seen[f[idx]] == 0:
                cnt -= 1
        f[idx] = color
        seen[color] += 1
        if seen[color] == 1:
            cnt += 1
        ans[i] = cnt
    return ans


def b131_4(queries: List[List[int]]) -> List[bool]:
    # TODO 线段树
    ...


def w399_1(nums1: List[int], nums2: List[int], k: int) -> int:
    ans = 0
    for x in nums1:
        for y in nums2:
            if x % (y * k) == 0:
                ans += 1
    return ans


def w399_2(word: str) -> str:
    comp = []
    last = '$'
    cnt = 1
    for x in word:
        if x != last or cnt == 9:
            comp.append(str(cnt))
            comp.append(last)
            cnt = 1
            last = x
        else:
            cnt += 1
    comp.append(str(cnt))
    comp.append(last)
    return ''.join(comp)[2:]


def w399_3(nums1: List[int], nums2: List[int], k: int) -> int:
    cnt = defaultdict(int)
    for x in nums1:
        if x % k:
            continue
        x //= k
        for d in range(1, math.isqrt(x) + 1):
            if x % d:
                continue
            cnt[d] += 1
            if d * d < x:
                cnt[x // d] += 1
    return sum(cnt[x] for x in nums2)


def w399_3_2(nums1: List[int], nums2: List[int], k: int) -> int:
    cnt1 = Counter(x // k for x in nums1 if x % k == 0)
    if not cnt1:
        return 0
    ans = 0
    u = max(cnt1)
    for i, c in Counter(nums2).items():
        s = sum(cnt1[j] for j in range(i, u + 1, i))
        ans += s * c
    return ans


def w399_4():
    # TODO 线段树
    ...


def w400_1(s: str) -> int:
    chairs = 0
    mx = 0
    for ch in s:
        if ch == "E":
            chairs += 1
        else:
            chairs = chairs - 1 if chairs > 0 else 0
        mx = max(mx, chairs)
    return mx


def w400_2(days: int, meetings: List[List[int]]) -> int:
    meetings.sort(key=lambda x: x[1], reverse=True)
    ans = 0
    last = days + 1
    for start, end in meetings:
        if end < last - 1:
            ans += last - end - 1
            last = start
        else:
            last = min(start, last)
    return ans + last - 1


def w400_3(s: str) -> str:
    indexes = [[] for _ in range(26)]
    removes = set()
    for i, c in enumerate(s):
        if c != '*':
            x = ord(c) - ord('a')
            indexes[x].append(i)
        else:
            removes.add(i)
            for j in range(26):
                if len(indexes[j]) > 0:
                    removes.add(indexes[j].pop())
                    break
    ans = []
    for i, c in enumerate(s):
        if i in removes:
            continue
        ans.append(c)
    return ''.join(ans)


def w400_4(nums: List[int], k: int) -> int:
    @cache
    def dfs(i, nd):
        if i == len(nums):
            return abs(k - nd)
        res = min(abs(k - nd), dfs(i + 1, nums[i]))  # i开始新的子数组
        res = min(res, dfs(i + 1, nd | nums[i]))  # 继续子数组
        return res

    ans = dfs(0, nums[0])
    dfs.cache_clear()
    return ans


def w400_4_2(nums: List[int], k: int) -> int:
    ans = inf
    # O(nlogU) U = max(nums)
    for i, x in enumerate(nums):
        ans = min(ans, abs(k - x))
        for j in range(i - 1, -1, -1):
            # 如果 nums[j] 包含于 x, 那么 j 及其左侧所有数都不会被更新
            if nums[j] | x == nums[j]:
                break
            # 最多执行logU次
            nums[j] |= x
            ans = min(ans, abs(nums[j] - k))
    return ans


def b132_1(s: str) -> str:
    ls = list(s)
    ans = []
    for i in range(len(s)):
        if ls[i].isdigit():
            ans.pop()
        else:
            ans.append(ls[i])
    return ''.join(ans)


def b132_2(skills: List[int], k: int) -> int:
    f = {}
    for i, x in enumerate(skills):
        f[x] = i
    if k >= len(skills) - 1:
        return f[max(skills)]
    deq = deque(skills)
    cnt = 0
    while cnt < k:
        if deq[1] > deq[0]:
            tmp = deq.popleft()
            cnt = 1
            deq.append(tmp)
        else:
            cnt += 1
            tmp = deq.popleft()
            tmp2 = deq.popleft()
            deq.appendleft(tmp)
            deq.append(tmp2)
    return f[deq[0]]


def b132_3(nums: List[int], k: int) -> int:
    @cache
    def dfs(i, cnt, last, begin):
        if cnt > k:
            return -inf
        if i == len(nums):
            return 0
        if not begin:
            res1 = dfs(i + 1, cnt, last, False)
            res2 = dfs(i + 1, cnt, nums[i], True) + 1
            return res1 if res1 > res2 else res2
        elif last == nums[i]:
            return dfs(i + 1, cnt, last, True) + 1
        else:
            res1 = dfs(i + 1, cnt + 1, nums[i], True) + 1
            res2 = dfs(i + 1, cnt, last, True)
            return res1 if res1 > res2 else res2

    ans = dfs(0, 0, 0, False)
    dfs.cache_clear()
    return ans


def b132_4(nums: List[int], k: int) -> int:
    @cache
    def dfs(i, cnt, last):
        if cnt > k:
            return -inf
        if i == len(nums):
            return 0
        if last == -1:
            res1 = dfs(i + 1, cnt, last)
            res2 = dfs(i + 1, cnt, nums[i]) + 1
            return res1 if res1 > res2 else res2
        elif last == nums[i]:
            return dfs(i + 1, cnt, last) + 1
        else:
            res2 = dfs(i + 1, cnt, last)
            res1 = dfs(i + 1, cnt + 1, nums[i]) + 1
            return res1 if res1 > res2 else res2

    ans = dfs(0, 0, -1)
    dfs.cache_clear()
    return ans


def w401_1(n: int, k: int) -> int:
    cnt = 0
    d = [1, -1]
    x = 0
    cur = 0
    while cnt < k:
        cur = cur + d[x]
        cnt += 1
        if cur == n - 1 and x == 0:
            x = 1
        elif cur == 0 and x == 1:
            x = 0
    return cur


def w401_2(n: int, k: int) -> int:
    mod_factor = 10 ** 9 + 7
    cnt = 1
    ans = [1] * n
    while cnt <= k:
        tmp = sum(ans) % mod_factor
        for i in range(n - 1, -1, -1):
            tmp = (tmp + mod_factor - ans[i]) % mod_factor
            ans[i] = (ans[i] + tmp) % mod_factor
        cnt += 1
    return ans[-1]


def w401_3(rewardValues: List[int]) -> int:
    rewardValues.sort()

    @cache
    def dfs(i, _sum):
        if i >= len(rewardValues):
            return 0
        res1 = dfs(i + 1, _sum)
        idx = bisect_right(rewardValues, _sum + rewardValues[i])
        res2 = dfs(idx, _sum + rewardValues[i]) + rewardValues[i]
        return max(res1, res2)

    ans = dfs(0, 0)
    dfs.cache_clear()
    return ans


def w401_4(rewardValues: List[int]) -> int:
    rewardValues.sort()

    @cache
    def dfs(i, _sum):
        if i >= len(rewardValues):
            return 0
        res1 = dfs(i + 1, _sum)
        idx = bisect_right(rewardValues, _sum + rewardValues[i])
        res2 = dfs(idx, _sum + rewardValues[i]) + rewardValues[i]
        return max(res1, res2)

    ans = dfs(0, 0)
    dfs.cache_clear()
    return ans


def w403_1(nums: List[int]) -> float:
    nums.sort()
    average = inf
    for i in range(len(nums) // 2):
        average = min(average, (nums[i] + nums[len(nums) - 1 - i]) / 2)
    return average


def w403_2(grid: List[List[int]]) -> int:
    mx_x, mx_y = 0, 0
    mn_x, mn_y = len(grid), len(grid[0])
    for i, row in enumerate(grid):
        for j, num in enumerate(row):
            if num == 1:
                mx_x, mx_y = max(i, mx_x), max(j, mx_y)
                mn_x, mn_y = min(i, mn_x), min(j, mn_y)
    return (mx_x - mn_x + 1) * (mx_y - mn_y + 1)


def w403_3(nums: List[int]) -> int:
    @cache
    def dfs(i, flip):
        if i == len(nums):
            return 0
        x = -nums[i] if flip else nums[i]
        # 下一个数是否翻转
        t = x + max(dfs(i + 1, False), dfs(i + 1, ~flip))
        print(t)
        return t

    ans = dfs(0, False)
    dfs.cache_clear()
    return ans


def w403_4():
    ...


def w404_1(red: int, blue: int) -> int:
    cnt = 1
    flag = True
    ans1 = 0
    t1, t2 = red, blue
    while True:
        if flag and red >= cnt:
            ans1 += 1
            red -= cnt
        elif (not flag) and blue >= cnt:
            ans1 += 1
            blue -= cnt
        else:
            break
        flag = not flag
        cnt += 1
    cnt = 1
    flag = True
    ans2 = 0
    red, blue = t1, t2
    while True:
        if flag and blue >= cnt:
            ans2 += 1
            blue -= cnt
        elif (not flag) and red >= cnt:
            ans2 += 1
            red -= cnt
        else:
            break
        flag = not flag
        cnt += 1
    return max(ans1, ans2)


def w404_2(nums: List[int]) -> int:
    ans0 = 0
    ans1 = 0
    for i in range(len(nums)):
        nums[i] = nums[i] % 2
        if nums[i] == 0:
            ans0 += 1
        else:
            ans1 += 1
    ans2 = 1
    cur = nums[0]
    for x in nums[1:]:
        if x ^ cur == 1:
            ans2 += 1
            cur = x
    return max(ans0, ans1, ans2)


def w404_3_2(nums: List[int], k: int) -> int:
    for i in range(len(nums)):
        nums[i] = nums[i] % k

    @cache
    def dfs(i, res):
        if i >= len(nums):
            return 0
        t = nums[i]
        for j in range(i + 1, len(nums)):
            if (t + nums[j]) % k == res:
                return 1 + dfs(j, res)
        return 1

    ans = 0
    for i in range(k):
        for j in range(len(nums)):
            if ans > len(nums) - j + 1:
                break
            ans = max(ans, dfs(j, i))

    dfs.cache_clear()
    return ans


def w404_3(nums: List[int], k: int) -> int:
    for i in range(len(nums) - 1, -1, -1):
        nums[i] = nums[i] % k
    ans = 0
    for i in range(len(nums)):
        if ans > len(nums) - i + 1:
            return ans
        t1 = nums[i]
        for j in range(i + 1, len(nums)):
            if ans > len(nums) - j + 2:
                break
            t2 = nums[j]
            t = (t1 + t2) % k
            cnt = 2
            for x in nums[j + 1:]:
                if (x + t2) % k == t:
                    cnt += 1
                    t2 = x
            ans = max(ans, cnt)
    return ans


def w404_4():
    ...


def w406_1(nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
    dummy_head = ListNode()
    dummy_head.next = head
    seen = set(nums)
    p = dummy_head
    while p.next is not None:
        q = p.next
        if q.val in seen:
            p.next = q.next
        else:
            p = q
    return dummy_head.next


def w406_2():
    ...


def w406_3(m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)

    @cache
    def dfs(x, y):
        if x == m - 1 and y == n - 1:
            return 0
        if x == m - 1:
            return dfs(x, y + 1) + verticalCut[y] * (x + 1)
        if y == n - 1:
            return dfs(x + 1, y) + horizontalCut[x] * (y + 1)
        return min(dfs(x + 1, y) + horizontalCut[x] * (y + 1), dfs(x, y + 1) + verticalCut[y] * (x + 1))

    ans = dfs(0, 0)
    dfs.cache_clear()
    return ans


def w406_4(m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)
    f = [[0] * n for _ in range(m)]
    for i in range(1, m):
        f[i][0] = f[i - 1][0] + horizontalCut[i - 1]
    for j in range(1, n):
        f[0][j] = f[0][j - 1] + verticalCut[j - 1]
    for i in range(1, m):
        for j in range(1, n):
            f[i][j] = min(f[i - 1][j] + horizontalCut[i - 1] * (j + 1), f[i][j - 1] + verticalCut[j - 1] * (i + 1))
    return f[-1][-1]


def w406_4_2(m: int, n: int, horizontalCut: List[int], verticalCut: List[int]) -> int:
    horizontalCut.sort(reverse=True)
    verticalCut.sort(reverse=True)
    f = [0] * n
    for j in range(1, n):
        f[j] = f[j - 1] + verticalCut[j - 1]
    for i in range(1, m):
        f[0] = f[0] + horizontalCut[i - 1]
        pre = f[0]
        for j in range(1, n):
            f[j] = min(f[j] + horizontalCut[i - 1] * (j + 1), pre + verticalCut[j - 1] * (i + 1))
            pre = f[j]
    return f[-1]


def w407_1():
    ...


def w407_2(s: str) -> bool:
    tmplt = 'aeiou'
    for x in s:
        if x in tmplt:
            return True
    return False


def w407_3(s: str) -> int:
    cnt = 0
    ans = 0
    able = False
    idx = s.find("1")
    for x in s[idx:]:
        if x == "0":
            able = True
        else:
            if able:
                ans += cnt
                able = False
            cnt += 1
    if able:
        ans += cnt
    return ans


def w407_4(nums: List[int], target: List[int]) -> int:
    # arr = [x - y for x, y in zip(target, nums)]
    # if len(arr) == 1:
    #     return arr[0]
    # ans = arr[0]
    # valley = min(arr[0], arr[1])
    # for i in range(1, len(arr) - 1):
    #     if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
    #         ans += arr[i] - valley
    #     elif arr[i] < arr[i - 1] and arr[i] < arr[i + 1]:
    #         valleys.append(i)
    ...